package advanced.class_append;

import java.util.Arrays;
import java.util.Stack;

// 单调栈
public class Code_02_SpecialStack {

    // 问题一：给定一个数组，请你返回每个元素右边第一个大于它的元素,如果不存在则返回-1
    public static int[] getFirstRightMax(int[] arr) {
        if(arr == null || arr.length == 0) return null;
        // 创建一个栈结构
        Stack<Integer> stack = new Stack<Integer>();
        int[] res = new int[arr.length];
        int i = 0;
        while(i < arr.length) {
            if(stack.isEmpty() || arr[stack.peek()] >= arr[i]) {
                stack.push(i);
                i++;
            }else{
                res[stack.pop()] = arr[i];
            }
        }
        // 遍历走完之后，栈中可能还剩余数组
        while(!stack.isEmpty()){
            res[stack.pop()] = -1;
        }
        return res;
    }

    // 问题二：给定一个数组，请你返回每个元素左边第一个大于它的元素,如果不存在则返回-1
    public static int[] getFirstLeftMax(int[] arr) {
        if(arr == null || arr.length == 0) return null;
        Stack<Integer> stack = new Stack<Integer>();
        int[] res = new int[arr.length];
        int i = 0;
        while(i < arr.length) {
            if(stack.isEmpty() || arr[stack.peek()] >= arr[i]) {
                stack.push(i);
                i++;
            }else{
                res[stack.pop()] = stack.isEmpty() ? -1 : arr[stack.peek()];
            }
        }
        while(!stack.isEmpty()){
            res[stack.pop()] = stack.isEmpty() ? -1 : arr[stack.peek()];
        }
        return res;
    }

    //LeeCode84 借用单调栈的思想求解柱状图中的最大矩形面积
    public static int largestRectangleArea(int[] heights) {
        // 首先进行边界条件判端
        if(heights == null || heights.length == 0) return 0;
        if(heights.length == 1) return heights[0];
        // 创建一个单调栈
        Stack<Integer> stack = new Stack<Integer>();
        int index = 0;
        int maxArea = 0;
        while(index < heights.length){
            if(stack.isEmpty()){
                stack.push(index++);
            }else{
                if(heights[stack.peek()] <= heights[index]){
                    stack.push(index++);
                }else{
                    // 取出当前栈顶元素对应的高度
                    int topHeight = heights[stack.pop()];
                    // 获取左边一个数据的索引，这个数据和当前的index之间肯定可以构成构成高度为height的矩阵
                    int leftIndex = stack.isEmpty() ? -1 : stack.peek();
                    // 更新maxArea
                    maxArea = Math.max(maxArea,(index - leftIndex - 1) * topHeight);
                }
            }
        }
        // 循环遍历结束时，index == arr.length; 还需要将栈中剩余的数据全部考虑进去
        while (!stack.isEmpty()) {
            int topHeight = heights[stack.pop()];
            int leftIndex = stack.isEmpty() ? -1 : stack.peek();
            maxArea = Math.max(maxArea,(index - leftIndex - 1) * topHeight);
        }
        return maxArea;
    }


    static class Node{
        int value;
        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    /**
     * 左神算法进阶班第三课，单调栈的衍生题
     * 求数组的maxTree
     * @param arr
     */
    public Node getMaxTree(int[] arr) {
        // 首先进行边界条件判断
        if(arr == null || arr.length == 0) return null;
        if(arr.length == 1) return new Node(arr[0]);
        // 创建单调栈
        Stack<Integer> stack = new Stack<Integer>();
        int index = 0;
        while(index < 0) {

        }
        return null;
    }



    public static void main(String[] args) {
        int[] arr = new int[]{1,5,3,6,4,8,9,10};
        int[] res1 = getFirstLeftMax(arr);
        int[] res2 = getFirstRightMax(arr);
        System.out.println(Arrays.toString(res1));
        System.out.println(Arrays.toString(res2));
    }

}
